It is typical for database management systems to include an optimizer program or routine that formulates execution plans for queries submitted to a database. Query execution plans are formulated with a goal of efficiently processing the database query, to optimize usage of various computing resources. Furthermore, query execution plans can have execution plan sub-trees (hereinafter referred to simply as “sub-trees”), some of which can be restarted. For example, restartable sub-trees may be formulated as part of a query execution plan for a query that includes a correlation sub-query or correlation predicate.
A common scenario in which restartable sub-trees are formulated involves probe-type operations, such as FILTER and NESTED-LOOPS JOIN operations. In such an operation, as part of the execution of the query, a row from a data table may flow up from a main or primary sub-tree (sometimes referred to herein as a “left” sub-tree) and probe into another secondary sub-tree (sometimes referred to herein as a “right” sub-tree) to test a condition based on the current row. The following example query illustrates a sub-query with a correlation that is executed as a filter, i.e., a correlation sub-query:                SELECT A.c1, A.c3, A.c4        FROM A        WHERE A.c1 in                    (SELECT B.c1 FROM B, C WHERE B.c2=C.c2 and B.c3=A.c3 and C.c4=A.c4).                        
In the preceding query, table A can be referred to as the primary table, and tables B and C as the secondary tables. The correlation sub-query includes the following three predicates:                B.c2=C.c2 (a join predicate);        B.c3=A.c3 (a correlation predicate); and        C.c4=A.c4 (a correlation predicate).Hence, each correlation predicate specifies a correlation between a secondary table and the primary table.        
In an execution plan for the preceding query, a left sub-tree might be formulated for a scan of the primary table A and a right sub-tree might be formulated for the correlation sub-query, which includes the join of the secondary tables B and C as well as the correlation predicate between primary table A and secondary table B and the correlation predicate between primary table A and secondary table C. Therefore, during execution of the query, a table scan of table A fetches a row from table A that meets the criteria of the left sub-tree, which is then probed into the right sub-tree to fetch any rows from the join of tables B and C that meet the criteria of the correlation predicates of the right sub-tree.
In executing the query, the right sub-tree is restarted, and rows are fetched, for each probe into the right sub-tree. When parallel processing is utilized for a query, that is, when multiple parallel server processes execute the query, a right sub-tree is likely executed in parallel. In this scenario, for each probe from table A, the right sub-tree representing the correlation sub-query is restarted and executed in parallel. Parallel restart and execution of a sub-tree may not be beneficial in some cases. For example, in situations in which the restart involves significant overhead (i.e., latency) or in which the enhanced speed offered by parallel processing, with respect to the cost-per-fetch, is not appreciable, parallel processing may not benefit the overall query execution.
Parallel processing of some sub-trees may not be optimal because of the latency overhead associated with (1) starting parallel server processes to execute a given sub-tree, and (2) allocating the processes to perform various parts of the given sub-tree, including joining and processing various portions of the secondary tables. Restarting a sub-tree for each probe would incur this latency overhead for each probe into the sub-tree. Another reason that parallel processing of restartable sub-trees may not be beneficial is because the scalability of parallel processing of a given sub-tree, that is, the ability to quickly reach a steady-state of execution for the multiple processes, may not be significant enough to justify using a large number of parallel server processes.
Based on the foregoing, there is a clear need for a mechanism for optimizing the processing of restartable sub-trees of a query execution plan. There is a more specific need for a mechanism to determine whether processing of restartable sub-trees would benefit from parallel processing by multiple server processes.